package com.lw.leetcode.tree.a;

import com.lw.leetcode.tree.TreeNode;

/**
 * 563. 二叉树的坡度
 *
 * @Author liw
 * @Date 2021/4/19 15:38
 * @Version 1.0
 */
public class FindTilt {


    public static void main(String[] args) {
        // [4,2,9,3,5,null,7]
        TreeNode a = new TreeNode(4);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(9);
        TreeNode d = new TreeNode(3);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        int tilt = new FindTilt().findTilt(a);
        System.out.println(tilt);
    }

    private int sum = 0;

    public int findTilt(TreeNode root) {
        find(root);
        return sum;
    }

    public int find(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int a = find(node.left);
        int b = find(node.right);
        if (a > b) {
            sum += (a - b);
        } else {
            sum += (b - a);
        }
        return a + b + node.val;
    }


}
